// 3.插入排序

// 思路：

//  从第一个元素开始，该元素可以认为已经被排序
//  取出下一个元素 temp，在已经排序的元素序列中从后向前扫描
//  如果该元素（已排序的元素）大于新元素 temp，将该元素移到下一位置
//  重复上一个步骤，直到找到已排序的元素小于或者等于新元素 temp 的位置
//  将新元素插入到该位置后, 重复上面的步骤

// 插入排序的比较次数:

//  第一趟时, 需要的最多次数是 1, 第二趟最多次数是 2, 依次类推, 最后一趟是 N-1 次.
//  因此是 1 + 2 + 3 + ... + N - 1 = N \* (N - 1) / 2.
//  然而每趟发现插入点之前, 平均只有全体数据项的一半需要进行比较.
//  我们可以除以 2 得到 N \* (N - 1) / 4. 所以相对于选择排序, 插入排序的比较次数是少了一半的.

//  大 O 表示法

//  比较次数：O(N^2)
//  交换次数：O(N)
// function insertionSort(arr) {
//   let length = arr.length;
//   for (let i = 1; i < length; i++) {
//     let j = i;
//     let temp = arr[i]; //当前值
//     while (j > 0 && arr[j - 1] > temp) {
//       arr[j] = arr[j - 1];
//       j--;
//     }
//     [temp, arr[j]] = [arr[j], temp];
//   }
//   return arr;
// }

const insertionSort = (arr) => {
  let length = arr.length;
  if (length === 0) {
    // 数组为空异常
    return null;
  }
  // 从第二个元素开始往前开始比较
  for (let i = 1; i < length; i++) {
    let j = i;
    // 暂存当前值
    let temp = arr[i];
    // while循环找到temp应该在的位置
    while (j > 0 && temp < arr[j - 1]) {
      // 把arr[j - 1]元素向后移动一个位置 在前面留出一个位置空间
      arr[j] = arr[j - 1];
      j--;
    }
    // 交换位置
    [temp, arr[j]] = [arr[j], temp];
  }
  return arr;
};

const test = [765, 234, 547, 241, 62, 124, 6, 232, 3, 2];
console.log(insertionSort(test));
